﻿#pragma once
#include "Index.h"
class PreimageSizeOfFactorialZeroesFunction
{
#define NumType long long
public:
	/**
	 * 阶乘函数后K个零.
	 *
	 * f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * ... * x，且 0! = 1 。
	 * 例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
     * 给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
	 */
	int preimageSizeFZF(int k)
	{
		const auto lower = lowerBound(k);
		int ans = 0;
		for (int i = 0; trailingZeroes(lower + i) == static_cast<unsigned int>(k); ++i)
			ans++;
		return ans;
	}

	//阶乘后的零.
	//给定一个整数 n ，返回 n! 结果中尾随零的数量。
	unsigned int trailingZeroes(NumType n)
	{
		unsigned int ans = 0;
		while (n)
		{
			ans += n / 5;
			n /= 5;
		}
		return ans;
	}

	//返回第一个数x,满足 trailingZeroes(x)==k
	unsigned int lowerBound(int k)
	{
		NumType left = 0, right = 5LL * k;
		NumType result = right;
		while (left <= right)
		{
			const auto mid = left + ((right - left) >> 1);
			const auto trailingZero = trailingZeroes(mid);
			if (trailingZero >= k)
			{
				result = mid;
				right = mid - 1;
			}
			else
			{
				left = mid + 1;
			}
		}
		return result;
	}
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(MyTestTest, MyTestTest)
{
	PreimageSizeOfFactorialZeroesFunction s;
	EXPECT_EQ(s.preimageSizeFZF(0) , 6);
}
#endif